package gsw.tool.datastructure.table;

/**
 * 哈希表
 *
 * @param <K>
 * @param <V>
 */
public class HashMap<K, V> {
    // 默认数组大小16，必须为2的幂
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    // 默认填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 节点数组
    Node<K, V>[] table;
    // 节点数组的大小
    int threshold;
    // 元素的个数
    int size;

    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();
        map.put("a", "晓敏1");
        map.put("b", "晓敏2");
        map.put("c", "晓敏3");
        map.put("a", "晓敏11");
        System.out.println(map.get("a"));
        System.out.println(map.remove("c"));
    }

    public HashMap() {
    }

    public HashMap(int initCapacity) {
        this.threshold = tableSizeFor(initCapacity);
    }

    /**
     * 返回2的幂
     *
     * @param cap
     * @return
     */
    private int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : n + 1;
    }

    /**
     * 添加元素
     * 添加的key必须实现hashCode()，否则不能映射地址。
     *
     * @param k 键
     * @param v 值
     * @return
     */
    public V put(K k, V v) {
        //初始化成员属性
        initTable();
        //允许key为null
        if (k == null) {
            return putNullKey(v);
        }
        //获取hash值
        int hash = hash(k);
        //映射到数组下标
        int index = getIndex(hash, table.length);
        //键不可以重复
        for (Node<K, V> node = table[index]; node != null; node = node.next) {
            if (hash == node.hash && (node.key == k || node.key.equals(k))) {
                V old = node.value;
                node.value = v;
                return old;
            }
        }
        //添加到哈希表
        addEntry(hash, k, v, index);
        return null;
    }

    /**
     * 添加为key为null的元素
     *
     * @param v
     * @return
     */
    private V putNullKey(V v) {
        for (Node<K, V> node = table[0]; node != null; node = node.next) {
            if (node.key == null) {
                V old = node.value;
                node.value = v;
                return old;
            }
        }
        addEntry(0, null, v, 0);
        return null;
    }

    /**
     * 添加实体
     *
     * @param hash
     * @param k
     * @param v
     * @param index
     */
    private void addEntry(int hash, K k, V v, int index) {
        //动态扩容
        if (size >= threshold && table[index] != null) {
            checkSize();
            hash = (k == null) ? 0 : hash(k);
            index = getIndex(hash, table.length);
        }
        //获取指定位置的节点
        Node<K, V> e = table[index];
        Node<K, V> newNode = new Node<K, V>(hash, k, v, e);
        table[index] = newNode;
        size++;
    }

    /**
     * 根据key获取Value
     *
     * @param key
     * @return
     */
    public V get(Object key) {
        if (key == null) {
            return getNullKey();
        }
        Node<K, V> node = getEntry(key);
        return (node == null) ? null : node.value;
    }

    /**
     * 获取key对应节点
     *
     * @param key
     * @return
     */
    private Node<K, V> getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key);
        int index = getIndex(hash, table.length);
        for (Node<K, V> node = table[index]; node != null; node = node.next) {
            if (hash == node.hash && (node.key == key || node.key.equals(key))) {
                return node;
            }
        }
        return null;
    }

    // 获取空key的value
    private V getNullKey() {
        if (size == 0) {
            return null;
        }
        for (Node<K, V> node = table[0]; node != null; node = node.next) {
            if (node.key == null) {
                return node.value;
            }
        }
        return null;
    }

    /**
     * 删除元素
     *
     * @param key
     * @return
     */
    public V remove(Object key) {
        if (size == 0) {
            return null;
        }
        int hash = (key == null) ? 0 : hash(key);
        int index = getIndex(hash, table.length);
        //先找到其头结点
        Node<K, V> pre = table[index];
        Node<K, V> now = pre;
        //根据key循环查找节点，找到后删除
        while (now != null) {
            Node<K, V> next = now.next;
            if (hash == now.hash && (now.key == key || (now.key != null && now.key.equals(key)))) {
                size--;
                if (pre == now) {
                    table[index] = next;
                } else {
                    pre.next = next;
                }
                return (now == null) ? null : now.value;
            }
            pre = now;
            now = next;
        }

        return (now == null) ? null : now.value;
    }

    // 根据hash值求位置
    private int getIndex(int hash, int length) {
        return hash & (length - 1);
    }

    // 检查大小
    private void checkSize() {
        if (size >= threshold) {
            int newCap = table.length << 2;
            Node<K, V>[] tab = new Node[newCap];
            for (Node<K, V> node : table) {
                while (node != null) {
                    Node<K, V> next = node.next;
                    int index = getIndex(node.hash, newCap);
                    node.next = tab[index];
                    tab[index] = node;
                    node = next;
                }
            }
            table = tab;
        }
    }

    /**
     * 初始化
     */
    private void initTable() {
        if (table == null) {
            if (threshold == 0) {
                table = new Node[DEFAULT_INITIAL_CAPACITY];
                threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
            } else {
                table = new Node[threshold];
            }
        }
    }

    /**
     * 获取Key的hash值
     *
     * @param key
     * @return
     */
    int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    /**
     * 自定义节点
     *
     * @param <K>
     * @param <V>
     */
    public static class Node<K, V> {
        final int hash;
        K key;
        V value;
        Node<K, V> next;

        public Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

    }
}
